/*
 * @Author: scl
 * @Date: 2023-08-21 23:53:13
 * @LastEditTime: 2023-08-22 16:11:38
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=34 lang=typescript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 *
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 *
 * algorithms
 * Medium (42.42%)
 * Likes:    2430
 * Dislikes: 0
 * Total Accepted:    835.4K
 * Total Submissions: 2M
 * Testcase Example:  '[5,7,7,8,8,10]\n8'
 *
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 
 * 示例 3：
 * 
 * 
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums 是一个非递减数组
 * -10^9 <= target <= 10^9
 * 
 * 
 */

// @lc code=start
function searchRange(nums: number[], target: number): number[] {
    const len=nums.length
    let mid,l=0,r=len-1
    while(nums[l]==target){
        l++
        if(nums[l]==undefined||nums[l]!=target)return [0,l-1]
    }
    while(nums[r]==target){
        r--
        if(nums[r]==undefined||nums[r]!=target)return [r+1,len-1]
    }
    while(l<r-1){
        mid=~~((r-l)/2+l)
        if(nums[mid]>target)r=mid
        else if(nums[mid]<target)l=mid
        else{
            l=mid,r=mid
            while(nums[l]==target){
                l--
            }
            while(nums[r]==target){
                r++
            }
            return [l+1,r-1]
        }
    }
    return [-1,-1]
};
// @lc code=end

